Legendre Symbol
Motivated by Euler's criterion, the Legendre symbol is a compact notation to encompass if \(a\) is a quadratic residue modulo \(p\).
Definition
For \(a\) and an odd prime \(p\), the Legendre symbol \((\frac{a}{p})\) is given by the function:
\[ \left(\frac{a}{p}\right) = \begin{cases}
1 & \text{if $a$ is a quadratic residue modulo} \ p \\
0 & \text{if} \ a \equiv 0 \pmod p\\
-1 & \text{if $a$ is a quadratic non-residue modulo} \ p \\
\end{cases}\]
This definition means, by Euler's criterion, that
\[ \left(\frac{a}{p}\right) \equiv a^{\frac{p - 1}{2}} \pmod p\]
noting that in the new case when \(a \equiv 0 \pmod p\) then \(a^{\frac{p - 1}{2}} \equiv 0 \pmod p\).
The Legendre symbol is multiplicative, which is very useful when computing it.